/*
    * dk.brics.automaton
    * 
    * Copyright (c) 2001-2009 Anders Moeller
    * All rights reserved.
    * 
    * Redistribution and use in source and binary forms, with or without
    * modification, are permitted provided that the following conditions
    * are met:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   * 3. The name of the author may not be used to endorse or promote products
   *    derived from this software without specific prior written permission.
   * 
   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   */
  
  package org.apache.lucene.util.automaton;
  
  import org.apache.lucene.util.ArrayUtil;
  import org.apache.lucene.util.BytesRef;
  import org.apache.lucene.util.BytesRefBuilder;
  import org.apache.lucene.util.IntsRef;
  import org.apache.lucene.util.IntsRefBuilder;
  import org.apache.lucene.util.RamUsageEstimator;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.BitSet;
  import java.util.Collection;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * Automata operations.
   * 
   * @lucene.experimental
   */
  final public class Operations {
    /**
     * Default maximum number of states that {@link Operations#determinize} should create.
     */
    public static final int DEFAULT_MAX_DETERMINIZED_STATES = 10000;
  
    private Operations() {}
  
    /**
     * Returns an automaton that accepts the concatenation of the languages of the
     * given automata.
     * <p>
     * Complexity: linear in total number of states.
     */
    static public Automaton concatenate(Automaton a1, Automaton a2) {
      return concatenate(Arrays.asList(a1, a2));
    }
  
    /**
     * Returns an automaton that accepts the concatenation of the languages of the
     * given automata.
     * <p>
     * Complexity: linear in total number of states.
     */
    static public Automaton concatenate(List<Automaton> l) {
      Automaton result = new Automaton();
  
      // First pass: create all states
      for(Automaton a : l) {
        if (a.getNumStates() == 0) {
          result.finishState();
          return result;
        }
        int numStates = a.getNumStates();
        for(int s=0;s<numStates;s++) {
          result.createState();
        }
      }
  
      // Second pass: add transitions, carefully linking accept
      // states of A to init state of next A:
      int stateOffset = 0;
      Transition t = new Transition();
      for(int i=0;i<l.size();i++) {
        Automaton a = l.get(i);
       int numStates = a.getNumStates();
 
       Automaton nextA = (i == l.size()-1) ? null : l.get(i+1);
 
       for(int s=0;s<numStates;s++) {
         int numTransitions = a.initTransition(s, t);
         for(int j=0;j<numTransitions;j++) {
           a.getNextTransition(t);
           result.addTransition(stateOffset + s, stateOffset + t.dest, t.min, t.max);
         }
 
         if (a.isAccept(s)) {
           Automaton followA = nextA;
           int followOffset = stateOffset;
           int upto = i+1;
           while (true) {
             if (followA != null) {
               // Adds a "virtual" epsilon transition:
               numTransitions = followA.initTransition(0, t);
               for(int j=0;j<numTransitions;j++) {
                 followA.getNextTransition(t);
                 result.addTransition(stateOffset + s, followOffset + numStates + t.dest, t.min, t.max);
               }
               if (followA.isAccept(0)) {
                 // Keep chaining if followA accepts empty string
                 followOffset += followA.getNumStates();
                 followA = (upto == l.size()-1) ? null : l.get(upto+1);
                 upto++;
               } else {
                 break;
               }
             } else {
               result.setAccept(stateOffset + s, true);
               break;
             }
           }
         }
       }
 
       stateOffset += numStates;
     }
 
     if (result.getNumStates() == 0) {
       result.createState();
     }
 
     result.finishState();
 
     return result;
   }
 
   /**
    * Returns an automaton that accepts the union of the empty string and the
    * language of the given automaton.  This may create a dead state.
    * <p>
    * Complexity: linear in number of states.
    */
   static public Automaton optional(Automaton a) {
     Automaton result = new Automaton();
     result.createState();
     result.setAccept(0, true);
     if (a.getNumStates() > 0) {
       result.copy(a);
       result.addEpsilon(0, 1);
     }
     result.finishState();
     return result;
   }
   
   /**
    * Returns an automaton that accepts the Kleene star (zero or more
    * concatenated repetitions) of the language of the given automaton. Never
    * modifies the input automaton language.
    * <p>
    * Complexity: linear in number of states.
    */
   static public Automaton repeat(Automaton a) {
     if (a.getNumStates() == 0) {
       // Repeating the empty automata will still only accept the empty automata.
       return a;
     }
     Automaton.Builder builder = new Automaton.Builder();
     builder.createState();
     builder.setAccept(0, true);
     builder.copy(a);
 
     Transition t = new Transition();
     int count = a.initTransition(0, t);
     for(int i=0;i<count;i++) {
       a.getNextTransition(t);
       builder.addTransition(0, t.dest+1, t.min, t.max);
     }
 
     int numStates = a.getNumStates();
     for(int s=0;s<numStates;s++) {
       if (a.isAccept(s)) {
         count = a.initTransition(0, t);
         for(int i=0;i<count;i++) {
           a.getNextTransition(t);
           builder.addTransition(s+1, t.dest+1, t.min, t.max);
         }
       }
     }
 
     return builder.finish();
   }
 
   /**
    * Returns an automaton that accepts <code>min</code> or more concatenated
    * repetitions of the language of the given automaton.
    * <p>
    * Complexity: linear in number of states and in <code>min</code>.
    */
   static public Automaton repeat(Automaton a, int count) {
     if (count == 0) {
       return repeat(a);
     }
     List<Automaton> as = new ArrayList<>();
     while (count-- > 0) {
       as.add(a);
     }
     as.add(repeat(a));
     return concatenate(as);
   }
   
   /**
    * Returns an automaton that accepts between <code>min</code> and
    * <code>max</code> (including both) concatenated repetitions of the language
    * of the given automaton.
    * <p>
    * Complexity: linear in number of states and in <code>min</code> and
    * <code>max</code>.
    */
   static public Automaton repeat(Automaton a, int min, int max) {
     if (min > max) {
       return Automata.makeEmpty();
     }
 
     Automaton b;
     if (min == 0) {
       b = Automata.makeEmptyString();
     } else if (min == 1) {
       b = new Automaton();
       b.copy(a);
     } else {
       List<Automaton> as = new ArrayList<>();
       for(int i=0;i<min;i++) {
         as.add(a);
       }
       b = concatenate(as);
     }
 
     Set<Integer> prevAcceptStates = toSet(b, 0);
     Automaton.Builder builder = new Automaton.Builder();
     builder.copy(b);
     for(int i=min;i<max;i++) {
       int numStates = builder.getNumStates();
       builder.copy(a);
       for(int s : prevAcceptStates) {
         builder.addEpsilon(s, numStates);
       }
       prevAcceptStates = toSet(a, numStates);
     }
 
     return builder.finish();
   }
 
   private static Set<Integer> toSet(Automaton a, int offset) {
     int numStates = a.getNumStates();
     BitSet isAccept = a.getAcceptStates();
     Set<Integer> result = new HashSet<Integer>();
     int upto = 0;
     while (upto < numStates && (upto = isAccept.nextSetBit(upto)) != -1) {
       result.add(offset+upto);
       upto++;
     }
 
     return result;
   }
   
   /**
    * Returns a (deterministic) automaton that accepts the complement of the
    * language of the given automaton.
    * <p>
    * Complexity: linear in number of states if already deterministic and
    *  exponential otherwise.
    * @param maxDeterminizedStates maximum number of states determinizing the
    *  automaton can result in.  Set higher to allow more complex queries and
    *  lower to prevent memory exhaustion.
    */
   static public Automaton complement(Automaton a, int maxDeterminizedStates) {
     a = totalize(determinize(a, maxDeterminizedStates));
     int numStates = a.getNumStates();
     for (int p=0;p<numStates;p++) {
       a.setAccept(p, !a.isAccept(p));
     }
     return removeDeadStates(a);
   }
   
   /**
    * Returns a (deterministic) automaton that accepts the intersection of the
    * language of <code>a1</code> and the complement of the language of
    * <code>a2</code>. As a side-effect, the automata may be determinized, if not
    * already deterministic.
    * <p>
    * Complexity: quadratic in number of states if a2 already deterministic and
    *  exponential in number of a2's states otherwise.
    */
   static public Automaton minus(Automaton a1, Automaton a2, int maxDeterminizedStates) {
     if (Operations.isEmpty(a1) || a1 == a2) {
       return Automata.makeEmpty();
     }
     if (Operations.isEmpty(a2)) {
       return a1;
     }
     return intersection(a1, complement(a2, maxDeterminizedStates));
   }
   
   /**
    * Returns an automaton that accepts the intersection of the languages of the
    * given automata. Never modifies the input automata languages.
    * <p>
    * Complexity: quadratic in number of states.
    */
   static public Automaton intersection(Automaton a1, Automaton a2) {
     if (a1 == a2) {
       return a1;
     }
     if (a1.getNumStates() == 0) {
       return a1;
     }
     if (a2.getNumStates() == 0) {
       return a2;
     }
     Transition[][] transitions1 = a1.getSortedTransitions();
     Transition[][] transitions2 = a2.getSortedTransitions();
     Automaton c = new Automaton();
     c.createState();
     LinkedList<StatePair> worklist = new LinkedList<>();
     HashMap<StatePair,StatePair> newstates = new HashMap<>();
     StatePair p = new StatePair(0, 0, 0);
     worklist.add(p);
     newstates.put(p, p);
     while (worklist.size() > 0) {
       p = worklist.removeFirst();
       c.setAccept(p.s, a1.isAccept(p.s1) && a2.isAccept(p.s2));
       Transition[] t1 = transitions1[p.s1];
       Transition[] t2 = transitions2[p.s2];
       for (int n1 = 0, b2 = 0; n1 < t1.length; n1++) {
         while (b2 < t2.length && t2[b2].max < t1[n1].min)
           b2++;
         for (int n2 = b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++)
           if (t2[n2].max >= t1[n1].min) {
             StatePair q = new StatePair(t1[n1].dest, t2[n2].dest);
             StatePair r = newstates.get(q);
             if (r == null) {
               q.s = c.createState();
               worklist.add(q);
               newstates.put(q, q);
               r = q;
             }
             int min = t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
             int max = t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
             c.addTransition(p.s, r.s, min, max);
           }
       }
     }
     c.finishState();
 
     return removeDeadStates(c);
   }
 
   /** Returns true if these two automata accept exactly the
    *  same language.  This is a costly computation!  Note
    *  also that a1 and a2 will be determinized as a side
    *  effect.  Both automata must be determinized and have
    *  no dead states! */
   public static boolean sameLanguage(Automaton a1, Automaton a2) {
     if (a1 == a2) {
       return true;
     }
     return subsetOf(a2, a1) && subsetOf(a1, a2);
   }
 
   // TODO: move to test-framework?
   /** Returns true if this automaton has any states that cannot
    *  be reached from the initial state or cannot reach an accept state.
    *  Cost is O(numTransitions+numStates). */
   public static boolean hasDeadStates(Automaton a) {
     BitSet liveStates = getLiveStates(a);
     int numLive = liveStates.cardinality();
     int numStates = a.getNumStates();
     assert numLive <= numStates: "numLive=" + numLive + " numStates=" + numStates + " " + liveStates;
     return numLive < numStates;
   }
 
   // TODO: move to test-framework?
   /** Returns true if there are dead states reachable from an initial state. */
   public static boolean hasDeadStatesFromInitial(Automaton a) {
     BitSet reachableFromInitial = getLiveStatesFromInitial(a);
     BitSet reachableFromAccept = getLiveStatesToAccept(a);
     reachableFromInitial.andNot(reachableFromAccept);
     return reachableFromInitial.isEmpty() == false;
   }
 
   // TODO: move to test-framework?
   /** Returns true if there are dead states that reach an accept state. */
   public static boolean hasDeadStatesToAccept(Automaton a) {
     BitSet reachableFromInitial = getLiveStatesFromInitial(a);
     BitSet reachableFromAccept = getLiveStatesToAccept(a);
     reachableFromAccept.andNot(reachableFromInitial);
     return reachableFromAccept.isEmpty() == false;
   }
 
   /**
    * Returns true if the language of <code>a1</code> is a subset of the language
    * of <code>a2</code>. Both automata must be determinized and must have no dead
    * states.
    * <p>
    * Complexity: quadratic in number of states.
    */
   public static boolean subsetOf(Automaton a1, Automaton a2) {
     if (a1.isDeterministic() == false) {
       throw new IllegalArgumentException("a1 must be deterministic");
     }
     if (a2.isDeterministic() == false) {
       throw new IllegalArgumentException("a2 must be deterministic");
     }
     assert hasDeadStatesFromInitial(a1) == false;
     assert hasDeadStatesFromInitial(a2) == false;
     if (a1.getNumStates() == 0) {
       // Empty language is alwyas a subset of any other language
       return true;
     } else if (a2.getNumStates() == 0) {
       return isEmpty(a1);
     }
 
     // TODO: cutover to iterators instead
     Transition[][] transitions1 = a1.getSortedTransitions();
     Transition[][] transitions2 = a2.getSortedTransitions();
     LinkedList<StatePair> worklist = new LinkedList<>();
     HashSet<StatePair> visited = new HashSet<>();
     StatePair p = new StatePair(0, 0);
     worklist.add(p);
     visited.add(p);
     while (worklist.size() > 0) {
       p = worklist.removeFirst();
       if (a1.isAccept(p.s1) && a2.isAccept(p.s2) == false) {
         return false;
       }
       Transition[] t1 = transitions1[p.s1];
       Transition[] t2 = transitions2[p.s2];
       for (int n1 = 0, b2 = 0; n1 < t1.length; n1++) {
         while (b2 < t2.length && t2[b2].max < t1[n1].min) {
           b2++;
         }
         int min1 = t1[n1].min, max1 = t1[n1].max;
 
         for (int n2 = b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++) {
           if (t2[n2].min > min1) {
             return false;
           }
           if (t2[n2].max < Character.MAX_CODE_POINT) {
             min1 = t2[n2].max + 1;
           } else {
             min1 = Character.MAX_CODE_POINT;
             max1 = Character.MIN_CODE_POINT;
           }
           StatePair q = new StatePair(t1[n1].dest, t2[n2].dest);
           if (!visited.contains(q)) {
             worklist.add(q);
             visited.add(q);
           }
         }
         if (min1 <= max1) {
           return false;
         }
       }
     }
     return true;
   }
 
   /**
    * Returns an automaton that accepts the union of the languages of the given
    * automata.
    * <p>
    * Complexity: linear in number of states.
    */
   public static Automaton union(Automaton a1, Automaton a2) {
     return union(Arrays.asList(a1, a2));
   }
 
   /**
    * Returns an automaton that accepts the union of the languages of the given
    * automata.
    * <p>
    * Complexity: linear in number of states.
    */
   public static Automaton union(Collection<Automaton> l) {
     Automaton result = new Automaton();
 
     // Create initial state:
     result.createState();
 
     // Copy over all automata
     for(Automaton a : l) {
       result.copy(a);
     }
     
     // Add epsilon transition from new initial state
     int stateOffset = 1;
     for(Automaton a : l) {
       if (a.getNumStates() == 0) {
         continue;
       }
       result.addEpsilon(0, stateOffset);
       stateOffset += a.getNumStates();
     }
 
     result.finishState();
 
     return removeDeadStates(result);
   }
 
   // Simple custom ArrayList<Transition>
   private final static class TransitionList {
     // dest, min, max
     int[] transitions = new int[3];
     int next;
 
     public void add(Transition t) {
       if (transitions.length < next+3) {
         transitions = ArrayUtil.grow(transitions, next+3);
       }
       transitions[next] = t.dest;
       transitions[next+1] = t.min;
       transitions[next+2] = t.max;
       next += 3;
     }
   }
 
   // Holds all transitions that start on this int point, or
   // end at this point-1
   private final static class PointTransitions implements Comparable<PointTransitions> {
     int point;
     final TransitionList ends = new TransitionList();
     final TransitionList starts = new TransitionList();
 
     @Override
     public int compareTo(PointTransitions other) {
       return point - other.point;
     }
 
     public void reset(int point) {
       this.point = point;
       ends.next = 0;
       starts.next = 0;
     }
 
     @Override
     public boolean equals(Object other) {
       return ((PointTransitions) other).point == point;
     }
 
     @Override
     public int hashCode() {
       return point;
     }
   }
 
   private final static class PointTransitionSet {
     int count;
     PointTransitions[] points = new PointTransitions[5];
 
     private final static int HASHMAP_CUTOVER = 30;
     private final HashMap<Integer,PointTransitions> map = new HashMap<>();
     private boolean useHash = false;
 
     private PointTransitions next(int point) {
       // 1st time we are seeing this point
       if (count == points.length) {
         final PointTransitions[] newArray = new PointTransitions[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
         System.arraycopy(points, 0, newArray, 0, count);
         points = newArray;
       }
       PointTransitions points0 = points[count];
       if (points0 == null) {
         points0 = points[count] = new PointTransitions();
       }
       points0.reset(point);
       count++;
       return points0;
     }
 
     private PointTransitions find(int point) {
       if (useHash) {
         final Integer pi = point;
         PointTransitions p = map.get(pi);
         if (p == null) {
           p = next(point);
           map.put(pi, p);
         }
         return p;
       } else {
         for(int i=0;i<count;i++) {
           if (points[i].point == point) {
             return points[i];
           }
         }
 
         final PointTransitions p = next(point);
         if (count == HASHMAP_CUTOVER) {
           // switch to HashMap on the fly
           assert map.size() == 0;
           for(int i=0;i<count;i++) {
             map.put(points[i].point, points[i]);
           }
           useHash = true;
         }
         return p;
       }
     }
 
     public void reset() {
       if (useHash) {
         map.clear();
         useHash = false;
       }
       count = 0;
     }
 
     public void sort() {
       // Tim sort performs well on already sorted arrays:
       if (count > 1) ArrayUtil.timSort(points, 0, count);
     }
 
     public void add(Transition t) {
       find(t.min).starts.add(t);
       find(1+t.max).ends.add(t);
     }
 
     @Override
     public String toString() {
       StringBuilder s = new StringBuilder();
       for(int i=0;i<count;i++) {
         if (i > 0) {
           s.append(' ');
         }
         s.append(points[i].point).append(':').append(points[i].starts.next/3).append(',').append(points[i].ends.next/3);
       }
       return s.toString();
     }
   }
 
   /**
    * Determinizes the given automaton.
    * <p>
    * Worst case complexity: exponential in number of states.
    * @param maxDeterminizedStates Maximum number of states created when
    *   determinizing.  Higher numbers allow this operation to consume more
    *   memory but allow more complex automatons.  Use
    *   DEFAULT_MAX_DETERMINIZED_STATES as a decent default if you don't know
    *   how many to allow.
    * @throws TooComplexToDeterminizeException if determinizing a creates an
    *   automaton with more than maxDeterminizedStates
    */
   public static Automaton determinize(Automaton a, int maxDeterminizedStates) {
     if (a.isDeterministic()) {
       // Already determinized
       return a;
     }
     if (a.getNumStates() <= 1) {
       // Already determinized
       return a;
     }
 
     // subset construction
     Automaton.Builder b = new Automaton.Builder();
 
     //System.out.println("DET:");
     //a.writeDot("/l/la/lucene/core/detin.dot");
 
     SortedIntSet.FrozenIntSet initialset = new SortedIntSet.FrozenIntSet(0, 0);
 
     // Create state 0:
     b.createState();
 
     LinkedList<SortedIntSet.FrozenIntSet> worklist = new LinkedList<>();
     Map<SortedIntSet.FrozenIntSet,Integer> newstate = new HashMap<>();
 
     worklist.add(initialset);
 
     b.setAccept(0, a.isAccept(0));
     newstate.put(initialset, 0);
 
     // like Set<Integer,PointTransitions>
     final PointTransitionSet points = new PointTransitionSet();
 
     // like SortedMap<Integer,Integer>
     final SortedIntSet statesSet = new SortedIntSet(5);
 
     Transition t = new Transition();
 
     while (worklist.size() > 0) {
       SortedIntSet.FrozenIntSet s = worklist.removeFirst();
       //System.out.println("det: pop set=" + s);
 
       // Collate all outgoing transitions by min/1+max:
       for(int i=0;i<s.values.length;i++) {
         final int s0 = s.values[i];
         int numTransitions = a.getNumTransitions(s0);
         a.initTransition(s0, t);
         for(int j=0;j<numTransitions;j++) {
           a.getNextTransition(t);
           points.add(t);
         }
       }
 
       if (points.count == 0) {
         // No outgoing transitions -- skip it
         continue;
       }
 
       points.sort();
 
       int lastPoint = -1;
       int accCount = 0;
 
       final int r = s.state;
 
       for(int i=0;i<points.count;i++) {
 
         final int point = points.points[i].point;
 
         if (statesSet.upto > 0) {
           assert lastPoint != -1;
 
           statesSet.computeHash();
           
           Integer q = newstate.get(statesSet);
           if (q == null) {
             q = b.createState();
             if (q >= maxDeterminizedStates) {
               throw new TooComplexToDeterminizeException(a, maxDeterminizedStates);
             }
             final SortedIntSet.FrozenIntSet p = statesSet.freeze(q);
             //System.out.println("  make new state=" + q + " -> " + p + " accCount=" + accCount);
             worklist.add(p);
             b.setAccept(q, accCount > 0);
             newstate.put(p, q);
           } else {
             assert (accCount > 0 ? true:false) == b.isAccept(q): "accCount=" + accCount + " vs existing accept=" +
               b.isAccept(q) + " states=" + statesSet;
           }
 
           // System.out.println("  add trans src=" + r + " dest=" + q + " min=" + lastPoint + " max=" + (point-1));
 
           b.addTransition(r, q, lastPoint, point-1);
         }
 
         // process transitions that end on this point
         // (closes an overlapping interval)
         int[] transitions = points.points[i].ends.transitions;
         int limit = points.points[i].ends.next;
         for(int j=0;j<limit;j+=3) {
           int dest = transitions[j];
           statesSet.decr(dest);
           accCount -= a.isAccept(dest) ? 1:0;
         }
         points.points[i].ends.next = 0;
 
         // process transitions that start on this point
         // (opens a new interval)
         transitions = points.points[i].starts.transitions;
         limit = points.points[i].starts.next;
         for(int j=0;j<limit;j+=3) {
           int dest = transitions[j];
           statesSet.incr(dest);
           accCount += a.isAccept(dest) ? 1:0;
         }
         lastPoint = point;
         points.points[i].starts.next = 0;
       }
       points.reset();
       assert statesSet.upto == 0: "upto=" + statesSet.upto;
     }
 
     Automaton result = b.finish();
     assert result.isDeterministic();
     return result;
   }
 
   /**
    * Returns true if the given automaton accepts no strings.
    */
   public static boolean isEmpty(Automaton a) {
     if (a.getNumStates() == 0) {
       // Common case: no states
       return true;
     }
     if (a.isAccept(0) == false && a.getNumTransitions(0) == 0) {
       // Common case: just one initial state
       return true;
     }
     if (a.isAccept(0) == true) {
       // Apparently common case: it accepts the damned empty string
       return false;
     }
     
     LinkedList<Integer> workList = new LinkedList<>();
     BitSet seen = new BitSet(a.getNumStates());
     workList.add(0);
     seen.set(0);
 
     Transition t = new Transition();
     while (workList.isEmpty() == false) {
       int state = workList.removeFirst();
       if (a.isAccept(state)) {
         return false;
       }
       int count = a.initTransition(state, t);
       for(int i=0;i<count;i++) {
         a.getNextTransition(t);
         if (seen.get(t.dest) == false) {
           workList.add(t.dest);
           seen.set(t.dest);
         }
       }
     }
 
     return true;
   }
   
   /**
    * Returns true if the given automaton accepts all strings.  The automaton must be minimized.
    */
   public static boolean isTotal(Automaton a) {
     return isTotal(a, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT);
   }
 
   /**
    * Returns true if the given automaton accepts all strings for the specified min/max
    * range of the alphabet.  The automaton must be minimized.
    */
   public static boolean isTotal(Automaton a, int minAlphabet, int maxAlphabet) {
     if (a.isAccept(0) && a.getNumTransitions(0) == 1) {
       Transition t = new Transition();
       a.getTransition(0, 0, t);
       return t.dest == 0
         && t.min == minAlphabet
         && t.max == maxAlphabet;
     }
     return false;
   }
   
   /**
    * Returns true if the given string is accepted by the automaton.  The input must be deterministic.
    * <p>
    * Complexity: linear in the length of the string.
    * <p>
    * <b>Note:</b> for full performance, use the {@link RunAutomaton} class.
    */
   public static boolean run(Automaton a, String s) {
     assert a.isDeterministic();
     int state = 0;
     for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) {
       int nextState = a.step(state, cp = s.codePointAt(i));
       if (nextState == -1) {
         return false;
       }
       state = nextState;
     }
     return a.isAccept(state);
   }
 
   /**
    * Returns true if the given string (expressed as unicode codepoints) is accepted by the automaton.  The input must be deterministic.
    * <p>
    * Complexity: linear in the length of the string.
    * <p>
    * <b>Note:</b> for full performance, use the {@link RunAutomaton} class.
    */
   public static boolean run(Automaton a, IntsRef s) {
     assert a.isDeterministic();
     int state = 0;
     for (int i=0;i<s.length;i++) {
       int nextState = a.step(state, s.ints[s.offset+i]);
       if (nextState == -1) {
         return false;
       }
       state = nextState;
     }
     return a.isAccept(state);
   }
 
   /**
    * Returns the set of live states. A state is "live" if an accept state is
    * reachable from it and if it is reachable from the initial state.
    */
   private static BitSet getLiveStates(Automaton a) {
     BitSet live = getLiveStatesFromInitial(a);
     live.and(getLiveStatesToAccept(a));
     return live;
   }
 
   /** Returns bitset marking states reachable from the initial state. */
   private static BitSet getLiveStatesFromInitial(Automaton a) {
     int numStates = a.getNumStates();
     BitSet live = new BitSet(numStates);
     if (numStates == 0) {
       return live;
     }
     LinkedList<Integer> workList = new LinkedList<>();
     live.set(0);
     workList.add(0);
 
     Transition t = new Transition();
     while (workList.isEmpty() == false) {
       int s = workList.removeFirst();
       int count = a.initTransition(s, t);
       for(int i=0;i<count;i++) {
         a.getNextTransition(t);
         if (live.get(t.dest) == false) {
           live.set(t.dest);
           workList.add(t.dest);
         }
       }
     }
 
     return live;
   }
 
   /** Returns bitset marking states that can reach an accept state. */
   private static BitSet getLiveStatesToAccept(Automaton a) {
     Automaton.Builder builder = new Automaton.Builder();
 
     // NOTE: not quite the same thing as what SpecialOperations.reverse does:
     Transition t = new Transition();
     int numStates = a.getNumStates();
     for(int s=0;s<numStates;s++) {
       builder.createState();
     }
     for(int s=0;s<numStates;s++) {
       int count = a.initTransition(s, t);
       for(int i=0;i<count;i++) {
         a.getNextTransition(t);
         builder.addTransition(t.dest, s, t.min, t.max);
       }
     }
     Automaton a2 = builder.finish();
 
     LinkedList<Integer> workList = new LinkedList<>();
     BitSet live = new BitSet(numStates);
     BitSet acceptBits = a.getAcceptStates();
     int s = 0;
     while (s < numStates && (s = acceptBits.nextSetBit(s)) != -1) {
       live.set(s);
       workList.add(s);
       s++;
     }
 
     while (workList.isEmpty() == false) {
       s = workList.removeFirst();
       int count = a2.initTransition(s, t);
       for(int i=0;i<count;i++) {
         a2.getNextTransition(t);
         if (live.get(t.dest) == false) {
           live.set(t.dest);
           workList.add(t.dest);
         }
       }
     }
 
     return live;
   }
 
   /**
    * Removes transitions to dead states (a state is "dead" if it is not
    * reachable from the initial state or no accept state is reachable from it.)
    */
   public static Automaton removeDeadStates(Automaton a) {
     int numStates = a.getNumStates();
     BitSet liveSet = getLiveStates(a);
 
     int[] map = new int[numStates];
 
     Automaton result = new Automaton();
     //System.out.println("liveSet: " + liveSet + " numStates=" + numStates);
     for(int i=0;i<numStates;i++) {
       if (liveSet.get(i)) {
         map[i] = result.createState();
         result.setAccept(map[i], a.isAccept(i));
       }
     }
 
     Transition t = new Transition();
 
     for (int i=0;i<numStates;i++) {
       if (liveSet.get(i)) {
         int numTransitions = a.initTransition(i, t);
         // filter out transitions to dead states:
         for(int j=0;j<numTransitions;j++) {
           a.getNextTransition(t);
           if (liveSet.get(t.dest)) {
             result.addTransition(map[i], map[t.dest], t.min, t.max);
           }
         }
       }
     }
 
     result.finishState();
     assert hasDeadStates(result) == false;
     return result;
   }
 
   /**
    * Finds the largest entry whose value is less than or equal to c, or 0 if
    * there is no such entry.
    */
   static int findIndex(int c, int[] points) {
     int a = 0;
     int b = points.length;
     while (b - a > 1) {
       int d = (a + b) >>> 1;
       if (points[d] > c) b = d;
       else if (points[d] < c) a = d;
       else return d;
     }
     return a;
   }
   
   /**
    * Returns true if the language of this automaton is finite.  The
    * automaton must not have any dead states.
    */
   public static boolean isFinite(Automaton a) {
     if (a.getNumStates() == 0) {
       return true;
     }
     return isFinite(new Transition(), a, 0, new BitSet(a.getNumStates()), new BitSet(a.getNumStates()));
   }
   
   /**
    * Checks whether there is a loop containing state. (This is sufficient since
    * there are never transitions to dead states.)
    */
   // TODO: not great that this is recursive... in theory a
   // large automata could exceed java's stack
   private static boolean isFinite(Transition scratch, Automaton a, int state, BitSet path, BitSet visited) {
     path.set(state);
     int numTransitions = a.initTransition(state, scratch);
     for(int t=0;t<numTransitions;t++) {
       a.getTransition(state, t, scratch);
       if (path.get(scratch.dest) || (!visited.get(scratch.dest) && !isFinite(scratch, a, scratch.dest, path, visited))) {
         return false;
       }
     }
     path.clear(state);
     visited.set(state);
     return true;
   }
   
   /**
    * Returns the longest string that is a prefix of all accepted strings and
    * visits each state at most once.  The automaton must be deterministic.
    * 
    * @return common prefix, which can be an empty (length 0) String (never null)
    */
   public static String getCommonPrefix(Automaton a) {
     if (a.isDeterministic() == false) {
       throw new IllegalArgumentException("input automaton must be deterministic");
     }
     StringBuilder b = new StringBuilder();
     HashSet<Integer> visited = new HashSet<>();
     int s = 0;
     boolean done;
     Transition t = new Transition();
     do {
       done = true;
       visited.add(s);
       if (a.isAccept(s) == false && a.getNumTransitions(s) == 1) {
         a.getTransition(s, 0, t);
         if (t.min == t.max && !visited.contains(t.dest)) {
           b.appendCodePoint(t.min);
           s = t.dest;
           done = false;
         }
       }
     } while (!done);
 
     return b.toString();
   }
   
   // TODO: this currently requites a determinized machine,
   // but it need not -- we can speed it up by walking the
   // NFA instead.  it'd still be fail fast.
   /**
    * Returns the longest BytesRef that is a prefix of all accepted strings and
    * visits each state at most once.  The automaton must be deterministic.
    * 
    * @return common prefix, which can be an empty (length 0) BytesRef (never null)
    */
   public static BytesRef getCommonPrefixBytesRef(Automaton a) {
     BytesRefBuilder builder = new BytesRefBuilder();
     HashSet<Integer> visited = new HashSet<>();
     int s = 0;
     boolean done;
     Transition t = new Transition();
     do {
       done = true;
       visited.add(s);
       if (a.isAccept(s) == false && a.getNumTransitions(s) == 1) {
         a.getTransition(s, 0, t);
         if (t.min == t.max && !visited.contains(t.dest)) {
           builder.append((byte) t.min);
           s = t.dest;
           done = false;
         }
       }
     } while (!done);
 
     return builder.get();
   }
 
   /** If this automaton accepts a single input, return it.  Else, return null.
    *  The automaton must be deterministic. */
   public static IntsRef getSingleton(Automaton a) {
     if (a.isDeterministic() == false) {
       throw new IllegalArgumentException("input automaton must be deterministic");
     }
     IntsRefBuilder builder = new IntsRefBuilder();
     HashSet<Integer> visited = new HashSet<>();
     int s = 0;
     Transition t = new Transition();
     while (true) {
       visited.add(s);
       if (a.isAccept(s) == false) {
         if (a.getNumTransitions(s) == 1) {
           a.getTransition(s, 0, t);
           if (t.min == t.max && !visited.contains(t.dest)) {
             builder.append(t.min);
             s = t.dest;
             continue;
           }
         }
       } else if (a.getNumTransitions(s) == 0) {
         return builder.get();
       }
 
       // Automaton accepts more than one string:
       return null;
     }
   }
 
   /**
    * Returns the longest BytesRef that is a suffix of all accepted strings.
    * Worst case complexity: exponential in number of states (this calls
    * determinize).
    * @param maxDeterminizedStates maximum number of states determinizing the
    *  automaton can result in.  Set higher to allow more complex queries and
    *  lower to prevent memory exhaustion.
    * @return common suffix, which can be an empty (length 0) BytesRef (never null)
    */
   public static BytesRef getCommonSuffixBytesRef(Automaton a, int maxDeterminizedStates) {
     // reverse the language of the automaton, then reverse its common prefix.
     Automaton r = Operations.determinize(reverse(a), maxDeterminizedStates);
     BytesRef ref = getCommonPrefixBytesRef(r);
     reverseBytes(ref);
     return ref;
   }
   
   private static void reverseBytes(BytesRef ref) {
     if (ref.length <= 1) return;
     int num = ref.length >> 1;
     for (int i = ref.offset; i < ( ref.offset + num ); i++) {
       byte b = ref.bytes[i];
       ref.bytes[i] = ref.bytes[ref.offset * 2 + ref.length - i - 1];
       ref.bytes[ref.offset * 2 + ref.length - i - 1] = b;
     }
   }
 
   /** Returns an automaton accepting the reverse language. */
   public static Automaton reverse(Automaton a) {
     return reverse(a, null);
   }
 
   /** Reverses the automaton, returning the new initial states. */
   static Automaton reverse(Automaton a, Set<Integer> initialStates) {
 
     if (Operations.isEmpty(a)) {
       return new Automaton();
     }
 
     int numStates = a.getNumStates();
 
     // Build a new automaton with all edges reversed
     Automaton.Builder builder = new Automaton.Builder();
 
     // Initial node; we'll add epsilon transitions in the end:
     builder.createState();
 
     for(int s=0;s<numStates;s++) {
       builder.createState();
     }
 
     // Old initial state becomes new accept state:
     builder.setAccept(1, true);
 
     Transition t = new Transition();
     for (int s=0;s<numStates;s++) {
       int numTransitions = a.getNumTransitions(s);
       a.initTransition(s, t);
       for(int i=0;i<numTransitions;i++) {
         a.getNextTransition(t);
         builder.addTransition(t.dest+1, s+1, t.min, t.max);
       }
     }
 
     Automaton result = builder.finish();
 
     int s = 0;
     BitSet acceptStates = a.getAcceptStates();
     while (s < numStates && (s = acceptStates.nextSetBit(s)) != -1) {
       result.addEpsilon(0, s+1);
       if (initialStates != null) {
         initialStates.add(s+1);
       }
       s++;
     }
 
     result.finishState();
 
     return result;
   }
 
   /** Returns a new automaton accepting the same language with added
    *  transitions to a dead state so that from every state and every label
    *  there is a transition. */
   static Automaton totalize(Automaton a) {
     Automaton result = new Automaton();
     int numStates = a.getNumStates();
     for(int i=0;i<numStates;i++) {
       result.createState();
       result.setAccept(i, a.isAccept(i));
     }
 
     int deadState = result.createState();
     result.addTransition(deadState, deadState, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT);
 
     Transition t = new Transition();
     for(int i=0;i<numStates;i++) {
       int maxi = Character.MIN_CODE_POINT;
       int count = a.initTransition(i, t);
       for(int j=0;j<count;j++) {
         a.getNextTransition(t);
         result.addTransition(i, t.dest, t.min, t.max);
         if (t.min > maxi) {
           result.addTransition(i, deadState, maxi, t.min-1);
         }
         if (t.max + 1 > maxi) {
           maxi = t.max + 1;
         }
       }
 
       if (maxi <= Character.MAX_CODE_POINT) {
         result.addTransition(i, deadState, maxi, Character.MAX_CODE_POINT);
       }
     }
 
     result.finishState();
     return result;
   }
 
   /** Returns the topological sort of all states reachable from
    *  the initial state.  Behavior is undefined if this
    *  automaton has cycles.  CPU cost is O(numTransitions),
    *  and the implementation is recursive so an automaton
    *  matching long strings may exhaust the java stack. */
   public static int[] topoSortStates(Automaton a) {
     if (a.getNumStates() == 0) {
       return new int[0];
     }
     int numStates = a.getNumStates();
     int[] states = new int[numStates];
     final BitSet visited = new BitSet(numStates);
     int upto = topoSortStatesRecurse(a, visited, states, 0, 0);
 
     if (upto < states.length) {
       // There were dead states
       int[] newStates = new int[upto];
       System.arraycopy(states, 0, newStates, 0, upto);
       states = newStates;
     }
 
     // Reverse the order:
     for(int i=0;i<states.length/2;i++) {
       int s = states[i];
       states[i] = states[states.length-1-i];
       states[states.length-1-i] = s;
     }
 
     return states;
   }
 
   private static int topoSortStatesRecurse(Automaton a, BitSet visited, int[] states, int upto, int state) {
     Transition t = new Transition();
     int count = a.initTransition(state, t);
     for (int i=0;i<count;i++) {
       a.getNextTransition(t);
       if (!visited.get(t.dest)) {
         visited.set(t.dest);
         upto = topoSortStatesRecurse(a, visited, states, upto, t.dest);
       }
     }
     states[upto] = state;
     upto++;
     return upto;
   }
 }